Stosch đã khởi đầu sự nghiệp quân sự của mình vào năm 1829 trong đội thiếu sinh, sau đó ông được phong quân hàm trung úy vào năm 1835 và học tại Trường Chiến tranh (Kriegsschule) kể từ năm 1839 cho đến năm 1842. Từ năm 1844 cho đến năm 1847, ông làm việc trong Cục đo đạc địa hình (topografischen Abteilung) của Bộ Tổng tham mưu và sau đó ông giữ các chức vụ tham mưu khác. Vào năm 1856, ông được lên quân hàm Thiếu tá vào năm 1861, ông được thăng cấp Đại tá, đồng thời là Tham mưu trưởng của Quân đoàn IV.

Vào năm 1866, ông được thăng quân hàm Thiếu tướng. Trong cuộc Chiến tranh Áo-Phổ, ông đã thực hiện xuất sắc nhiệm vụ của mình trên cương vị là Chủ nhiệm Tổng cục hậu cần (Oberquartiermeister) của Binh đoàn thứ hai, dưới sự thống lĩnh của Thái tử Friedrich Wilhelm. Cho đến năm 1870, ông là Giám đốc Khoa Kinh tế Quân sự trong Bộ Chiến tranh. Vào năm 1870, ông được phong cấp Thiếu tướng và được cử làm Quản đốc Lục quân (Generalintendant der Armee). Trong cuộc Chiến tranh Pháp-Đức, khi Đại Công tước xứ Mecklenburg-Schwerin được ủy nhiệm làm chỉ huy của một lực lượng tổng hợp vào cuối năm 1870, Stosch trên cương vị là Tham mưu trưởng của Mecklenburg nắm thực quyền chỉ huy đạo quân của vị đại công tước[2]. Sau khi cuộc chiến tranh chấm dứt vào năm 1871, ông nhậm chức Tham mưu trưởng của Lực lượng chiếm đóng (Besatzungsarmee) tại Pháp. Do những thành tích của ông trong cuộc chiến với Pháp, ông đã được ban tặng 100.000 thaler.

Kể từ tháng 1 năm 1872 cho đến tháng 3 năm 1873, Stosch là Bộ trưởng Bộ Hải quân Đế quốc Đức, đồng thời giữ chức vụ danh dự (Charakter) Bộ trưởng Nhà nước không bộ. Vào năm 1875, ông được thăng cấp Thượng tướng Bộ binh và Đô đốc. Ông là bạn của Thái tử Friedrich Wilhelm (tức vị "Hoàng đế 99 ngày" Friedrich III tương lai) và với tư cách là một người theo xu hướng Cựu tự do (Altliberale), ông giữ lập trường đối địch với chính sách đối nội của Thủ tướng Bismarck. Những bất đồng với Bismarck đã dẫn đến việc ông từ chức vào năm 1883. Mặc dù ông giành phần lớn thời gian của mình tại điền trang của ông ở Rheinland sau khi thoái chức, ông vẫn luôn giữ mối quan hệ với Thái tử. Vào ngày 31 tháng 3 năm 1883, như một động thái nhỏ chống lại vị Thủ tướng quyền uy, Friedrich và Thái tử phi Victoria đã vời Stosch đến dự một bữa tiệc chia tay riêng[5].

Stosch là chủ sở hữu của một xưởng rượu vang tại Mittelheim (Rheingau) và từ năm 1872 cho đến khi từ trần vào năm 1896, ông là một thành viên của Viện Quý tộc Phổ. Tên ông được đặt cho một hòn đảo ở Chile, đảo Stosch.